package main

import (
	"fmt"
	"strconv"
	"strings"
)

// 哈希表
type HashTable struct {
	Capacity int
	Table    []*Entry
}

// 添加元素
func (hashTable *HashTable) Put(key int, value interface{}) (oldValue interface{}, e error) {

	// 取模获取到元素应该放置的index索引
	index := key % hashTable.Capacity

	// 获取到该index的entry
	entry := hashTable.Table[index]

	if entry == nil {
		// 如果当前不存在，就创建一个新的放进去
		entry = &Entry{
			key:   key,
			value: value,
			next:  nil,
		}
		hashTable.Table[index] = entry
		return nil, nil
	}

	if entry.key == key {
		oldValue = entry.value
		entry.value = value
		return oldValue, nil
	}

	if entry.key > key {
		hashTable.Table[index] = &Entry{
			key:   key,
			value: value,
			next:  entry,
		}
		return nil, nil
	}

	for {

		if entry.next == nil || entry.next.key > key {
			newEntry := &Entry{
				key:   key,
				value: value,
				next:  entry.next,
			}
			entry.next = newEntry
			return nil, nil
		}

		if entry.next.key == key {
			oldValue = entry.next.value
			entry.next.value = value
			return oldValue, nil
		}

		entry = entry.next
	}
}

// 获取元素
func (hashTable *HashTable) Get(key int) (value interface{}) {

	// 取模获取到元素应该放置的index索引
	index := key % hashTable.Capacity

	// 获取到该index的entry
	entry := hashTable.Table[index]

	if entry == nil {
		return nil
	}

	for {
		if entry.key == key {
			return entry.value
		}

		if entry.next == nil {
			break
		}

		entry = entry.next
	}

	return nil
}

// 删除元素
func (hashTable *HashTable) Remove(key int) (value interface{}) {

	// 取模获取到元素应该放置的index索引
	index := key % hashTable.Capacity

	// 获取到该index的entry
	entry := hashTable.Table[index]

	if entry == nil || entry.key > key {
		return nil
	}

	if entry.key == key {
		hashTable.Table[index] = entry.next
		return entry.value
	}

	for {

		if entry.next == nil || entry.next.key > key {
			return nil
		}

		if entry.next.key == key {
			oldValue := entry.next.value
			entry.next = entry.next.next
			return oldValue
		}

		entry = entry.next
	}
}

// 格式化输出
func (hashTable *HashTable) String() string {

	result := ""

	for i, v := range hashTable.Table {
		if v != nil {
			result += "{"
			result += strconv.Itoa(i)
			result += ": "
			result += fmt.Sprintf("%v", v.String())
			result += "}\n"
		}
	}

	return strings.Trim(result, "\n")
}

// 封装元素，链式结构
type Entry struct {
	key   int
	value interface{}
	next  *Entry
}

// 格式化输出
func (entry *Entry) String() string {

	result := ""

	result += "{"
	result += "key: "
	result += fmt.Sprintf("%v", entry.key)
	result += ", "
	result += "value: "
	result += fmt.Sprintf("%v", entry.value)
	result += ", "
	result += "next: "
	result += fmt.Sprintf("%v", entry.next)
	result += "}"

	return result
}

// 创建一个HashTable
// capacity: 容量
func NewHashTable(capacity int) (hashTable *HashTable) {
	return &HashTable{
		Capacity: capacity,
		Table:    make([]*Entry, capacity),
	}
}

// 示例元素结构体
type Student struct {
	id       int
	name     string
	nickname string
}

// 覆盖String方法，格式化输出
func (student *Student) String() string {
	return fmt.Sprintf("{id=%d, nickname=%s, name=%s}", student.id, student.nickname, student.name)
}

func main() {

	// 创建一个HashTable
	hashTable := NewHashTable(16)

	// 创建元素
	//s0 := &Student{0, "晁盖", "托塔天王"}
	s1 := &Student{1, "宋江", "及时雨"}
	s2 := &Student{2, "卢俊义", "玉麒麟"}
	//s3 := &Student{3, "吴用", "智多星"}
	s14 := &Student{14, "武松", "行者"}
	//s10 := &Student{10, "柴进", "小旋风"}
	//s13 := &Student{13, "鲁智深", "花和尚"}
	//s22 := &Student{22, "李逵", "黑旋风"}
	//s22x := &Student{22, "李鬼", "黑旋风"}

	s17 := &Student{17, "杨志", "青面兽"}

	// 添加元素
	fmt.Println(hashTable.Put(s14.id, s14))
	fmt.Println(hashTable.Put(s14.id, s14))
	fmt.Println(hashTable.Put(s1.id, s1))
	fmt.Println(hashTable.Put(s1.id, &Student{1, "宋江", "呼保义"}))
	fmt.Println(hashTable.Put(s2.id, s2))
	fmt.Println(hashTable.Put(s2.id, s2))
	fmt.Println(hashTable.Put(s17.id, s17))

	fmt.Println(hashTable)

	// 获取元素
	fmt.Printf("获取%d元素: %v\n", 1, hashTable.Get(1))
	fmt.Printf("获取%d元素: %v\n", 2, hashTable.Get(2))
	fmt.Printf("获取%d元素: %v\n", 21, hashTable.Get(21))
	fmt.Printf("获取%d元素: %v\n", 17, hashTable.Get(17))

	// 移除元素
	fmt.Printf("移除%d元素: %v\n", 15, hashTable.Remove(15))
	fmt.Printf("获取%d元素: %v\n", 15, hashTable.Get(15))
}
